# gas  = [1,2,3,4,5]
# cost = [3,4,5,1,2]
# gas  = [2,3,4]
# cost = [3,4,3]
gas=[11,4,7,1,0]
cost=[2,5,5,9,1]

#时间上过不了
def canCompleteCircuit(gas,cost):
    queueList=[]
    for i in range(len(gas)):
        if gas[i]-cost[i]>=0:
            queueList.append([i,gas[i]-cost[i]])
    queueList.sort(key=lambda x:x[1])
    queueList.reverse()
    print(queueList)
    gasLen=len(gas)
    for (x,y) in queueList:
        can_reach = True
        print(x,y)
        loc=1
        rem=y
        while loc<=gasLen:
            rem+=gas[(x+loc)%gasLen]
            print("rem:",rem,"x+loc:",(x+loc)%gasLen)
            if rem>=cost[(x+loc)%gasLen]:
                rem-=cost[(x+loc)%gasLen]
            else:
                print(x,"走不通")
                can_reach=False
                break
            loc+=1
        if can_reach:
            return x
        else:
            continue
    return -1
def canCompleteCircuit1(gas,cost):
    gasLen=len(gas)
    spare=0
    minSpare=10000
    minIndex=0
    for i in range(gasLen):
        spare+=gas[i]-cost[i]
        if spare<minSpare:
            minSpare=spare
            minIndex=i
    #总油量小于总耗油量，那么就不可能可以到达，直接返回-1
    if spare<0:
        return -1
    else:
        return (minIndex+1)%gasLen




print(canCompleteCircuit1(gas,cost))

